package demo.DataStrucAndAlgo.recursion;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/23-07-23-15:34
 * @Description：demo.DataStrucAndAlgo.recursion    递归解决八皇后问题（回溯算法）
 * 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，
 *      即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法（92）。
 */

class Queen8{
    private int max=8;
    private int result[]=new int[max];

    /**
     * 回溯算法解决八皇后问题
     * @param n 第n个皇后，也表示第n行
     */
    public void resolve(int n){
        if (n==max){//在后续每次递归 n+1 ,n的初始值为0，所以当n==8时说明前8个皇后已经找到共存办法
            print();//打印找到的共存方法
            return;//结束本轮递归
        }
        for(int i=0;i<max;i++){//遍历每一行8个格，并判断与上一行的皇后冲突吗？
            result[n]=i;//记录第n行皇后的位置
            if (judge(n)){//判断冲突，true为不冲突
                resolve(n+1);//递归进行下一行皇后
            }
            //当判断为冲突时，将回溯到上一行皇后判断中，将其向前一位，继续重复操作
        }
    }

    /**
     * 判断冲突
     * @param n 获取第n行皇后，并与前n-1行皇后进行判断冲突
     * @return true为和平，false为冲突
     */
    private boolean judge(int n){
        for (int i=0;i<n;i++){//与前n-1行皇后进行判断列向，斜向冲突
            if (result[i]==result[n] || Math.abs(result[n]-result[i])==Math.abs(n-i)){//列向判断||斜向判断
                return false;
            }
        }
        return true;
    }

    /**
     * 打印八皇后问题解法
     */
    private void print(){
        for (int i=0;i<max;i++){
            System.out.print((result[i]+1)+" ");//由于数组是从0计数的，为了方便阅读+1
        }
        System.out.println();
    }
}

public class Recursion_Queen {
    public static void main(String[] args) {
        Queen8 queen = new Queen8();
        queen.resolve(2);
    }
}
